翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

promise problem : ウィキペディア英語版
promise problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs.〔(【引用サイトリンク】 Promise problem )〕 Unlike decision problems, the ''yes'' instances (the inputs for which an algorithm must return ''yes'') and ''no'' instances do not exhaust the set of all inputs. Intuitively, the algorithm has been ''promised'' that the input does indeed belong to set of ''yes'' instances or ''no'' instances. There may be inputs which are neither ''yes'' or ''no''. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.
==Formal definition==

A decision problem can be associated with a language L \subseteq \^
*, where the problem is to accept all inputs in L and reject all inputs not in L. For a promise problem, there are two languages, L_}, which must be disjoint, which means L_} = \varnothing, such that all the inputs in L_} are to be rejected. The set L_} is called the ''promise''. There are no requirements on the output if the input does not belong to the promise. If the promise equals \^
*, then this is also a decision problem, and the promise is said to be trivial.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「promise problem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.